package com.leetcode.algorithm.y22.m07.w3;

import java.util.PriorityQueue;

/**
 * 973. 最接近原点的 K 个点
 * 
 * https://leetcode.cn/problems/k-closest-points-to-origin/
 * 
 * @author jie.deng
 *
 */
class Question0973Solution03 {

	public int[][] kClosest(int[][] points, int k) {
		// 优先队列(堆)
		// PriorityQueue<K> K=new int[]{idx, distance*distance}
		PriorityQueue<int[]> queue = new PriorityQueue<>((x1, x2) -> (x1[1] - x2[1]));
		for (int i = 0; i < points.length; i++) {
			queue.offer(new int[] { i, points[i][0] * points[i][0] + points[i][1] * points[i][1] });
		}
		int[][] ans = new int[k][2];
		while (k > 0) {
			ans[k - 1] = points[queue.poll()[0]];
			k--;
		}
		return ans;
	}

}